/*
 * Copyright (c) 2008, Solido Systems
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 *
 * Neither the name of Solido Systems nor the names of its contributors may be
 * used to endorse or promote products derived from this software without
 * specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

package com.solidosystems.objectkitchen.index;

import java.io.*;
import java.util.*;

public class Node{
	private NodeManager manager;
	
	private long location;
	private long parentLocation;
	private long leftChildLocation;
	private long centerChildLocation;
	private long rightChildLocation;
	
	private long leftValueLocation;
	private long rightValueLocation;
	
	private IndexEntry leftValue;
	private IndexEntry rightValue;
	
	private long lastUsage;	
	
	public Node(NodeManager manager,long location,long parentLocation){
		this.manager=manager;
		this.location=location;
		this.parentLocation=parentLocation;
		leftChildLocation=-1;
		centerChildLocation=-1;
		rightChildLocation=-1;
		leftValueLocation=-1;
		rightValueLocation=-1;
		lastUsage=System.currentTimeMillis();
	}
	
	public int depth() throws IOException{
		int cnt=0;
		if(leftChildLocation>-1){
			cnt=getLeftChild().depth();
		}
		if(centerChildLocation>-1){
			int d=getCenterChild().depth();
			if(d>cnt)cnt=d;
		}
		if(rightChildLocation>-1){
			int d=getRightChild().depth();
			if(d>cnt)cnt=d;
		}
		cnt++;
		return cnt;
	}
	
	public List<IndexEntry> getAll() throws IOException{
		List<IndexEntry> list=new ArrayList<IndexEntry>();
		Node node=getLeftChild();
		if(node!=null){
			list.addAll(node.getAll());
		}
		if(leftValueLocation>-1)list.add(getLeftValue());
		node=getCenterChild();
		if(node!=null){
			list.addAll(node.getAll());
		}
		if(rightValueLocation>-1)list.add(getRightValue());
		node=getRightChild();
		if(node!=null){
			list.addAll(node.getAll());
		}
		return list;
	}
	
	public int count() throws IOException{
		int cnt=1;
		if(leftChildLocation>-1)cnt+=getLeftChild().count();
		if(centerChildLocation>-1)cnt+=getCenterChild().count();
		if(rightChildLocation>-1)cnt+=getRightChild().count();
		return cnt;
	}
	
	public long getLocation(){
		return location;
	}
	
	public void markUsage(){
		lastUsage=System.currentTimeMillis();
	}
	
	private Node createChild() throws IOException{
		return manager.createNode(this);
	}
	
	public void save() throws IOException{
		manager.saveNode(this);
	}
	
	private void setLeftValue(IndexEntry entry){
		leftValue=entry;
		leftValueLocation=entry.getLocation();
	}
	
	private void setRightValue(IndexEntry entry){
		rightValue=entry;
		rightValueLocation=entry.getLocation();
	}
	
	public void addIndexEntry(IndexEntry entry) throws IOException{
		// System.out.println("Adding "+entry.getHashCode()+" to "+location);
		// inspectNode();
		// Empty node?
		if(leftValueLocation==-1){
			// System.out.println(" Empty node");
			setLeftValue(entry);
			save();
			return;
		}
		// One value leaf?
		if(rightValueLocation==-1){
			// System.out.println(" One value leaf");
			if(entry.getHashCode()>getLeftValue().getHashCode()){
				setRightValue(entry);
			}else{
				setRightValue(getLeftValue());
				setLeftValue(entry);
			}
			save();
			return;
		}
		// Root node?
		if(parentLocation==-1){
			// System.out.println(" We are adding third value to the root node");
			Node left=createChild();
			Node right=createChild();
			if(entry.getHashCode()<getLeftValue().getHashCode()){
				left.setLeftValue(entry);
				right.setLeftValue(getRightValue());
			}else if(entry.getHashCode()>getRightValue().getHashCode()){
				left.setLeftValue(getLeftValue());
				setLeftValue(getRightValue());
				right.setLeftValue(entry);
			}else{
				left.setLeftValue(getLeftValue());
				setLeftValue(entry);
				right.setLeftValue(getRightValue());
			}
			removeRightValue();
			setLeftChild(left);
			setRightChild(right);
			left.save();
			right.save();
			save();
			return;
		}
		// Start dealing with the parent
		Node parent=getParent();
		if(parent.getChildCount()==2){
			// System.out.println(" Rerotating");
			IndexEntry s=entry;
			IndexEntry m=getLeftValue();
			IndexEntry l=getRightValue();

			// Weeee... bubble bobble bobble bubble... sort sort sort GO!
			if(m.getHashCode()<s.getHashCode()){
				IndexEntry tmp=s;
				s=m;
				m=tmp;
			}
			if(l.getHashCode()<m.getHashCode()){
				IndexEntry tmp=m;
				m=l;
				l=tmp;
			}
			if(m.getHashCode()<s.getHashCode()){
				IndexEntry tmp=s;
				s=m;
				m=tmp;
			}

			if(parent.leftChildLocation==location){
				// System.out.println("Left child action "+s.getHashCode()+" "+m.getHashCode()+" "+l.getHashCode());
				// we are the left child
				// System.out.println(parent.getTree());
				// parent.inspectNode();
				parent.setRightValue(parent.getLeftValue());
				parent.setLeftValue(m);
				Node center=parent.createChild();
				center.setLeftValue(l);
				center.save();
				parent.setCenterChild(center);
				parent.save();
				// parent.inspectNode();
				setLeftValue(s);
				removeRightValue();
				save();
				// System.out.println(parent.getTree());
				// System.out.println(manager.getNode(8).getTree());
				// throw new IOException("foo bar");
				return;
			}else{
				// System.out.println("right child action "+s.getHashCode()+" "+m.getHashCode()+" "+l.getHashCode());
				// we are the right child
				parent.setRightValue(m);
				Node center=parent.createChild();
				center.setLeftValue(s);
				center.save();
				parent.setCenterChild(center);
				parent.save();
				setLeftValue(l);
				removeRightValue();
				save();
				return;
			}
		}else{
			// System.out.println(" 3 child parent");
			Node center=parent.getCenterChild();
			Node left=parent.getLeftChild();
			Node right=parent.getRightChild();
			
			IndexEntry s=entry;
			IndexEntry m=getLeftValue();
			IndexEntry l=getRightValue();

			// Weeee... bubble bobble bobble bubble... sort sort sort GO!
			if(m.getHashCode()<s.getHashCode()){
				IndexEntry tmp=s;
				s=m;
				m=tmp;
			}
			if(l.getHashCode()<m.getHashCode()){
				IndexEntry tmp=m;
				m=l;
				l=tmp;
			}
			if(m.getHashCode()<s.getHashCode()){
				IndexEntry tmp=s;
				s=m;
				m=tmp;
			}
			
			if(center.noChildren()&&left.noChildren()&&right.noChildren()){
				if(parent.leftChildLocation==location){
					// We are left
					if(center.getRightValue()==null){
						center.setRightValue(center.getLeftValue());
						center.setLeftValue(parent.getLeftValue());
						parent.setLeftValue(l);
						setLeftValue(s);
						setRightValue(m);
						parent.save();
						center.save();
						save();
						return;
					}else if(right.getRightValue()==null){
						right.setRightValue(right.getLeftValue());
						right.setLeftValue(parent.getRightValue());
						parent.setRightValue(center.getRightValue());
						center.setRightValue(center.getLeftValue());
						center.setLeftValue(parent.getLeftValue());
						parent.setLeftValue(l);
						setLeftValue(s);
						setRightValue(m);
						right.save();
						parent.save();
						center.save();
						save();
						return;
					}else{
						splitCurrent(entry);
						return;
					}
				}else if(parent.centerChildLocation==location){
					// We are center
					if(left.getRightValue()==null){
						left.setRightValue(parent.getLeftValue());
						parent.setLeftValue(s);
						setLeftValue(m);
						setRightValue(l);
						left.save();
						parent.save();
						save();
						return;
					}else if(right.getRightValue()==null){
						right.setRightValue(right.getLeftValue());
						right.setLeftValue(parent.getRightValue());
						parent.setRightValue(l);
						setRightValue(m);
						setLeftValue(s);
						right.save();
						parent.save();
						save();
						return;
					}else{
						splitCurrent(entry);
						return;
					}
				}else{
					// We are right
					if((left.getRightValue()==null)&&(center.getRightValue()!=null)){
						left.setRightValue(parent.getLeftValue());
						parent.setLeftValue(center.getLeftValue());
						center.setLeftValue(center.getRightValue());
						center.setRightValue(parent.getRightValue());
						parent.setRightValue(s);
						setLeftValue(m);
						setRightValue(l);
						left.save();
						parent.save();
						center.save();
						save();
						return;
					}else if(center.getRightValue()==null){
						center.setRightValue(parent.getRightValue());
						parent.setRightValue(s);
						setLeftValue(m);
						setRightValue(l);
						center.save();
						parent.save();
						save();
						return;
					}else{
						splitCurrent(entry);
						return;
					}
				}
			}else{
				splitCurrent(entry);
				return;
			}
		}
	}
	
	private void splitCurrent(IndexEntry entry) throws IOException{
		Node left=createChild();
		Node right=createChild();
		if(entry.getHashCode()<getLeftValue().getHashCode()){
			left.setLeftValue(entry);
			right.setLeftValue(getRightValue());
		}else if(entry.getHashCode()>getRightValue().getHashCode()){
			left.setLeftValue(getLeftValue());
			setLeftValue(getRightValue());
			right.setLeftValue(entry);
		}else{
			left.setLeftValue(getLeftValue());
			setLeftValue(entry);
			right.setLeftValue(getRightValue());
		}
		removeRightValue();
		setLeftChild(left);
		setRightChild(right);
		left.save();
		right.save();
		save();
		return;
	}
	
	private void removeRightValue(){
		rightValue=null;
		rightValueLocation=-1;
	}
	
	public void inspectNode() throws IOException{
		System.out.println("Node "+location);
		if(leftValueLocation>-1){
			System.out.println(" + Left Value  : "+getLeftValue().getHashCode());
		}
		if(rightValueLocation>-1){
			System.out.println(" + Right Value : "+getRightValue().getHashCode());
		}
		System.out.println(" + Children    : "+leftChildLocation+","+centerChildLocation+","+rightChildLocation);
	}
	
	public String getTree() throws IOException{
		StringBuilder buf=new StringBuilder();
		buf.append(location);
		buf.append("<");
		IndexEntry entry=getLeftValue();
		if(entry!=null)buf.append(entry.getHashCode());
		buf.append("-");
		entry=getRightValue();
		if(entry!=null)buf.append(entry.getHashCode());
		buf.append(">(");
		Node left=getLeftChild();
		if(left!=null){
			buf.append(left.getTree());
		}else if(leftChildLocation>-1)System.out.println("!!! READ ERROR");
		buf.append(",");
		Node center=getCenterChild();
		if(center!=null){
			buf.append(center.getTree());
		}else if(centerChildLocation>-1)System.out.println("!!! READ ERROR");
		buf.append(",");
		Node right=getRightChild();
		if(right!=null){
			buf.append(right.getTree());
		}else if(rightChildLocation>-1)System.out.println("!!! READ ERROR");
		buf.append(")");
		return buf.toString();
	}
	
	public IndexEntry findEntry(int searchCode,byte[] searchId) throws IOException{
		// inspectNode();
		// Is this node empty?
		if(leftValueLocation==-1)return null;
		// Check left value
		if(noChildren()){
			IndexEntry entry=getLeftValue();
			if(searchCode==entry.getHashCode()){
				// is the left value the correct match?
				if(entry.matchesId(searchId)){
					return entry;
				}
			}
			if(rightValueLocation>-1){
				entry=getRightValue();
				if(searchCode==entry.getHashCode()){
					// is the left value the correct match?
					if(entry.matchesId(searchId)){
						return entry;
					}
				}
			}
			return null;
		}
		
		IndexEntry entry=getLeftValue();
		if(searchCode<entry.getHashCode()){
			return getLeftChild().findEntry(searchCode,searchId);
		}else{
			if(searchCode==entry.getHashCode()){
				// is the left value the correct match?
				if(entry.matchesId(searchId)){
					return entry;
				}
			}
		}
		if(rightValueLocation>-1){
			entry=getRightValue();
			if(searchCode>entry.getHashCode()){
				return getRightChild().findEntry(searchCode,searchId);
			}else if(searchCode==entry.getHashCode()){
				// is the right value the correct match?
				if(entry.matchesId(searchId)){
					return entry;
				}else{
					Node center=getCenterChild();
					if(center!=null){
						entry=center.findEntry(searchCode,searchId);
						if(entry!=null)return entry;
					}
					Node right=getRightChild();
					if(right!=null){
						entry=right.findEntry(searchCode,searchId);
						if(entry!=null)return entry;
					}
				}
			}else{
				return getCenterChild().findEntry(searchCode,searchId);
			}
		}else{
			return getRightChild().findEntry(searchCode,searchId);
		}
		return null;
	}
	
	public Node findLeaf(int search) throws IOException{
		// Is this node empty?
		if(leftValueLocation==-1)return this;
		// Is this a leaf?
		if(noChildren())return this;
		
		// Are we smaller than left?
		IndexEntry entry=getLeftValue();
		if(search<entry.getHashCode()){
			return getLeftChild().findLeaf(search);
		}
		// Is this a 2 node?
		if(rightValueLocation==-1){
			return getRightChild().findLeaf(search);
		}else{
			entry=getRightValue();
			if(search>entry.getHashCode()){
				return getRightChild().findLeaf(search);
			}else{
				return getCenterChild().findLeaf(search);
			}
		}
	}
	
	public boolean noChildren(){
		if(leftChildLocation>-1)return false;
		if(centerChildLocation>-1)return false;
		if(rightChildLocation>-1)return false;
		return true;
	}
	
	public int getChildCount(){
		if(leftChildLocation==-1)return 0;
		if(centerChildLocation>-1)return 3;
		return 2;
	}
	
	public Node getParent() throws IOException{
		if(parentLocation==-1)return null;
		return manager.getNode(parentLocation);
	}
	
	public Node getLeftChild() throws IOException{
		if(leftChildLocation==-1)return null;
		return manager.getNode(leftChildLocation);
	}
	
	public Node getCenterChild() throws IOException{
		if(centerChildLocation==-1)return null;
		return manager.getNode(centerChildLocation);
	}
	
	public Node getRightChild() throws IOException{
		if(rightChildLocation==-1)return null;
		return manager.getNode(rightChildLocation);
	}
	
	public IndexEntry getLeftValue() throws IOException{
		if(leftValueLocation==-1)return null;
		if(leftValue!=null)return leftValue;
		leftValue=manager.getIndexEntry(leftValueLocation);
		return leftValue;
	}
	
	public IndexEntry getRightValue() throws IOException{
		if(rightValueLocation==-1)return null;
		if(rightValue!=null)return rightValue;
		rightValue=manager.getIndexEntry(rightValueLocation);
		return rightValue;
	}
	
	public void setLeftChild(Node left){
		this.leftChildLocation=left.getLocation();
	}
	
	public void setCenterChild(Node center){
		this.centerChildLocation=center.getLocation();
	}
	
	public void setRightChild(Node right){
		this.rightChildLocation=right.getLocation();
	}
	
	public void writeToFile(RandomAccessFile file) throws IOException{
		file.writeLong(parentLocation);
		
		file.writeLong(leftChildLocation);
		file.writeLong(centerChildLocation);
		file.writeLong(rightChildLocation);
		
		file.writeLong(leftValueLocation);
		file.writeLong(rightValueLocation);
		file.getFD().sync();
	}
	
	public void writeToStream(DataOutputStream file) throws IOException{
		file.writeLong(parentLocation);
		
		file.writeLong(leftChildLocation);
		file.writeLong(centerChildLocation);
		file.writeLong(rightChildLocation);
		
		file.writeLong(leftValueLocation);
		file.writeLong(rightValueLocation);
		file.flush();
	}
	
	public static Node readFromFile(NodeManager manager,RandomAccessFile file) throws IOException{
		long location=file.getFilePointer();
		
		long parentLocation=file.readLong();
		
		long leftChildLocation=file.readLong();
		long centerChildLocation=file.readLong();
		long rightChildLocation=file.readLong();
		
		long leftValueLocation=file.readLong();
		long rightValueLocation=file.readLong();
		
		Node node=new Node(manager,location,parentLocation);
		
		node.leftChildLocation=leftChildLocation;
		node.centerChildLocation=centerChildLocation;
		node.rightChildLocation=rightChildLocation;
		
		node.leftValueLocation=leftValueLocation;
		node.rightValueLocation=rightValueLocation;
		return node;
	}
}